package com.github.yangyishe.p500;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 452. 用最少数量的箭引爆气球
 * https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/?envType=study-plan-v2&envId=top-interview-150
 *
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
 *
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 *
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 *
 *
 * 示例 1：
 *
 * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
 * 输出：2
 * 解释：气球可以用2支箭来爆破:
 * -在x = 6处射出箭，击破气球[2,8]和[1,6]。
 * -在x = 11处发射箭，击破气球[10,16]和[7,12]。
 * 示例 2：
 *
 * 输入：points = [[1,2],[3,4],[5,6],[7,8]]
 * 输出：4
 * 解释：每个气球需要射出一支箭，总共需要4支箭。
 * 示例 3：
 *
 * 输入：points = [[1,2],[2,3],[3,4],[4,5]]
 * 输出：2
 * 解释：气球可以用2支箭来爆破:
 * - 在x = 2处发射箭，击破气球[1,2]和[2,3]。
 * - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
 *
 *
 * 提示:
 *
 * 1 <= points.length <= 105
 * points[i].length == 2
 * -231 <= xstart < xend <= 231 - 1
 */
public class Problem452 {
    public static void main(String[] args) {
        int[][] points=new int[][]{
                {1,2},
                {2,3},
                {3,4},
                {4,5},
        };
        Problem452 problem452 = new Problem452();
        int i = problem452.findMinArrowShots(points);
        System.out.println(i);
    }

    /**
     * 思路:
     * 使用贪心算法的思路.
     * 1. 先将区间按照结束点从小到大进行排序
     *  ->至少应该有一支箭, 应该设在最左区间内, 而最贪心的做法, 就是设在最左区间的结束点
     *  ->射出这支箭后, 将所有开始点早于或等于这支箭位置的气球算作已被射爆. 继续向右找未被射爆(开始点大于该位置)的最近气球的结束点, 记为第二支箭的位置
     *  -> 以此类推, 直到所有气球都被射爆
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        // 排序. 具体步骤略. 时间复杂度nlog(n)
        // 此处排序, 如果使用给定的api, 如Integer.compare(), 速度反而慢. 在这里就不纠结了.
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] > o2[1]) {
                    return 1;
                } else if (o1[1] < o2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        int arrowCount=1;
        int lastArrowPosition=points[0][1];
        for(int i=1;i<points.length;i++){
            int[] point=points[i];
            if(point[0]<=lastArrowPosition){
                continue;
            }
            arrowCount++;
            lastArrowPosition=point[1];

        }

        return arrowCount;
    }
}
